/* CPP Assignemnt 3 (COSC1152-2011-S2)
 * Elliott O'Dea-Joyce s3074110@student.rmit.edu.au
 * Ross Nye s9455459@student.rmit.edu.au
 */

#include "fact.h"
#include <string>

// Factory class for the algorithms, pass algo type get Prims or Kruskals
GraphFactory* GraphFactory::create(int type)
{
	switch(type)
	{
		case 0:
			return KruskalsFactory::create();
		case 1:
			return PrimsFactory::create();
	}
	throw std::runtime_error("Invalid algorithm type");
	return NULL;
}


GraphFactory* KruskalsFactory::create()
{
	return new KruskalsFactory();
}



GraphFactory* PrimsFactory::create()
{
	return new PrimsFactory();
}

// Generates the MST from the graph details supplied with MakeGraph strategy
void KruskalsFactory::generateMST(MakeGraph* mg)
{
	// setup for boost
	using namespace boost;
  typedef adjacency_list < vecS, vecS, undirectedS,
    no_property, property < edge_weight_t, float > > Graph;
  typedef graph_traits < Graph >::edge_descriptor Edge;
  typedef graph_traits < Graph >::vertex_descriptor Vertex;
  
  // this vector store the resulting MST
	std::vector <Edge> spanning_tree;

	std::cout << "Using Kruskals algorithm with ";
	std::cout << mg->getStratName() << std::endl;
			
	// setup boost graph 
	Graph g(mg->getEdges()->begin(), mg->getEdges()->end(), 
			mg->getWeights()->begin(), mg->getNumVertex());
			
#if DEBUG
	std::cout << "Graph size = " << num_vertices(g) << "\n";
#endif

	// run boost kruskal aglo to calculate MST
	kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

	endTimer();

#if DEBUG
	std::cout << "Kruskal mg with v.size = " << mg->getVertex()->size();
	std::cout << " and " << mg->getNumVertex() << " vertices and ";
	std::cout << mg->getNumEdges() << " candidate edges and ";
	std::cout << spanning_tree.size() << " mst edges" << std::endl;
	std::cout << "Writing ouput SVG created using Kruskals algorithm" << std::endl;
#endif

	// setup output file name and open outfile file stream
	std::ostringstream fname;
	fname << "mst-" << mg->getNumVertex() << "-Kruskals-" << mg->getStratName()
			 << ".svg";
	std::cout << "Writing ouput to " << fname.str() << std::endl;
	
  std::ofstream fout(fname.str());
	if (!fout.is_open())
		throw std::runtime_error("Unable to open file for saving ");

	// write the SVG tag and a comment about the graph
	fout << "<svg viewBox='0 0 1 1' width='500' height='500'";
	fout << " xmlns='http://www.w3.org/2000/svg'>\n";

  fout << "<!-- MST has " << mg->getNumVertex() << " vertices and ";
  fout << mg->getNumEdges() << " complete edges and ";
  fout << spanning_tree.size() << " mst edges -->" << std::endl;
  
#if 1
	// iterate over edges in MST and write to file
  for(Edge ed : spanning_tree)
  {
  	int vA = source(ed, g);
  	int vB = target(ed, g);
  	
  	// write comment about the edge to the file
  	fout << "<!-- Edge: Vertex #" << vA << " to #" << vB;
  	fout << " V(" << mg->getVertex()->at(vA).first;
  	fout << ", " << mg->getVertex()->at(vA).second << ") to ";
  	fout << "V(" << mg->getVertex()->at(vB).first;
  	fout << ", " << mg->getVertex()->at(vB).second << ") -->" << std::endl;
  	
  	// write svg line element to the file
		fout << "<line stroke='black' stroke-width='0.001' ";
  	fout << "x1='" << mg->getVertex()->at(vA).first;
  	fout << "' y1='" << mg->getVertex()->at(vA).second << "' ";
  	fout << "x2='" << mg->getVertex()->at(vB).first;
  	fout << "' y2='" << mg->getVertex()->at(vB).second << "'/>" << std::endl;
  }
#else
  graph_traits<Graph>::edge_iterator eiter, eiter_end;
  for (boost::tie(eiter, eiter_end) = edges(g); eiter != eiter_end; ++eiter)
 	  if (std::find(spanning_tree.begin(), spanning_tree.end(), *eiter) 
 	  		!= spanning_tree.end())
 	  {
 	  // FIXME these loops iters etc all based on the original K example - 
 	  // I cant see it being wrong this code works the same as the code in Prims..
 	  // in fact we should make it a method.. but for some reason K is wrong.... 
	  int vA = source(*eiter, g);
	  int vB = target(*eiter, g);
  	fout << "<!-- Edge: Vertex #" << vA << " to #" << vB;
  	fout << " V(" << mg->getVertex()->at(vA).first;
  	fout << ", " << mg->getVertex()->at(vA).second << ") to ";
  	fout << "V(" << mg->getVertex()->at(vB).first;
  	fout << ", " << mg->getVertex()->at(vB).second << ") -->" << std::endl;

		fout << "<line stroke='black' stroke-width='0.001' ";
  	fout << "x1='" << mg->getVertex()->at(vA).first;
  	fout << "' y1='" << mg->getVertex()->at(vA).second << "' ";
  	fout << "x2='" << mg->getVertex()->at(vB).first;
  	fout << "' y2='" << mg->getVertex()->at(vB).second << "'/>" << std::endl;
  	}
#endif

  fout << "</svg>\n";
  fout.close();

}

// Generates the MST from the graph details supplied with MakeGraph strategy
// using Prims
void PrimsFactory::generateMST(MakeGraph* mg)
{
	using namespace boost;
	typedef adjacency_list < vecS, vecS, undirectedS, 
													property<vertex_distance_t, float>, 
													property < edge_weight_t, float > > Graph;

	std::cout << "Using Prims algorithm with ";
	std::cout << mg->getStratName() << std::endl;
	
	// setup boost graph
	Graph g(mg->getEdges()->begin(), mg->getEdges()->end(), 
			mg->getWeights()->begin(), mg->getNumVertex());
  property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g);
  std::vector < graph_traits < Graph >::vertex_descriptor > p(num_vertices(g));
	
	// use boost prims algo to calculate the mst
	prim_minimum_spanning_tree(g, &p[0]);
	endTimer();

#if DEBUG
  std::cout << "Prims has " << mg->getNumVertex() << " vertices and ";
  std::cout << mg->getNumEdges() << " candidate edges and ";
  std::cout << p.size() -1 << " mst edges" << std::endl;
 	std::cout << "Writing ouput SVG created using Prims algorithm" << std::endl;
#endif
	
	// write output to file
	std::ostringstream fname;
	fname << "mst-" << mg->getNumVertex() << "-Prims-" <<
			 mg->getStratName() << ".svg";
	std::cout << "Writing ouput to " << fname.str() << std::endl;

  std::ofstream fout(fname.str());
	if (!fout.is_open())
		throw std::runtime_error("Unable to open file for saving");

	// write svg tag and comment about the graph
	fout << "<svg viewBox='0 0 1 1' width='500' height='500'";
	fout << " xmlns='http://www.w3.org/2000/svg'>\n";

  fout << "<!-- MST has " << mg->getNumVertex() << " vertices and ";
  fout << mg->getNumEdges() << " candidate edges and ";
  fout << p.size()-1 << " mst edges -->" << std::endl;


	// iterate over the graph and write the edges to file
	for (std::size_t i = 0; i != p.size(); ++i)
		if (p[i] != i)
		{
			int vA = p[i];
			int vB = i;
			
			// write comment tag containing the edge details to svg
			fout << "<!-- Edge: Vertex #" << vA << " to #" << vB;
  		fout << " V(" << mg->getVertex()->at(vA).first;
  		fout << ", " << mg->getVertex()->at(vA).second << ") to ";
  		fout << "V(" << mg->getVertex()->at(vB).first;
  		fout << ", " << mg->getVertex()->at(vB).second << ") -->" << std::endl;
  		
  		// write svg line tag details to svg file
  		fout << "<line stroke='black' stroke-width='0.001' ";
  		fout << "x1='" << mg->getVertex()->at(vA).first;
  		fout << "' y1='" << mg->getVertex()->at(vA).second << "' ";
  		fout << "x2='" << mg->getVertex()->at(vB).first;
  		fout << "' y2='" << mg->getVertex()->at(vB).second << "'/>" << std::endl;
		}
	fout << "</svg>" << std::endl;
	fout.close();
}
